Low density parity check (LDPC) codes are linear error control codes with sparse parity check matrices and long block lengths that have been found to be an efficient method for transmitting messages over a noisy transmission channel while attaining performance near the Shannon limit. In particular, LDPC codes are used in many digital television standards (whether for terrestrial, satellite, cable or mobile use), such as DVB (Digital Video Broadcast)-T2, DVB-S2, DVB-C2, and China Terrestrial Television Broadcasting (CTTB), and other wireless standards, such as WiMax™ (IEEE 802.16) and some WiFi™ (IEEE 802.11.n) variants.
In general a message is encoded into a plurality of LDPC codes at a transmitter based on a parity check matrix and then transmitted across a channel. The LDPC codes are received at a receiver where an LDPC decoder attempts to decode each of the received LDPC codes using the parity check matrix. Most commercial LDPC decoders implement an iterative decoding technique based on the concept of belief propagation. In these techniques each single parity check (SPC) of the parity check matrix is decoded separately using soft-in-soft-out (SISO) techniques using message passing.
Instead of estimating the decoded message from the hard-decision value, each iteration involves estimating the codeword and performing parity checks on the estimated codeword. The output is a soft decision, which may be in the form of a Log-Likelihood Ratio (LLR). The sign of an LLR indicates whether a particular bit is more likely to be a “1” or “0” and the magnitude of the LLR represents the confidence or probability that the bit has the likely value. Generally, as more iterations are performed the number of failed parity checks decreases. However, since these decoding techniques implement a minimum searching technique, in many cases the decoder can get stuck within a local minimum and never converge to the correct codeword.
The embodiments described below are not limiting of implementations which solve any or all of the disadvantages of known LDPC decoding systems.